package binarysearch;

/**
 * @description:
 * @author: jhy
 * @time: 2021/4/22 16:48
 */

/*
二分查找(非递归)：容易出错的地方
(1)循环退出的地方是left <= right，而不是left < right
(2)mid的取值，可以为mid = (left + right) / 2,
    如果left和right比较大，为了防止溢出，可以mid = left + (right - left) / 2;
    也可以mid = (left + right) >>> 1;//无符号右移一位
(3)left和right的更新为：left = mid + 1;right = mid - 1;
 */
public class BinarySearchDemo1 {

    public static void main(String[] args) {

        int[] nums = {1, 2, 5, 7, 8, 9};
        int i = binarySearch(nums, 7);
        System.out.println(i);

    }

    //二分查找，如果找到，返回目标值target在数组中的索引nums
    //如果找不到，返回-1
    public static int binarySearch(int[] nums,int target){
        if(nums == null){
            return -1;
        }
        //左指针
        int left = 0;
        //右指针
        int right = nums.length - 1;
        while (left <= right){

            int mid = left + (right - left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){ //target在mid的左边
                right = mid - 1;
            }else { //target在mid的右边
                left = mid + 1;
            }
        }
        return -1;
    }
}
